package com.example.system.class13;

/**
 * @Date 2022/8/2
 * @Author Jonathan
 * @Description 是否是满二叉树 2^height(高度)-1==nodes(节点数)
 */
public class Code05_IsFull {
    private static int index = 0;

    // 1 8 12 n n 2 n n 4 3 n n 9 n n
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 8, 12, null, null, 2, null, null, 4, 3, null, null, 9, null, null};
        Node bt = createBT(arr);
        System.out.println(isFull(bt));
//        Integer[] myArr = new Integer[]{1, 8, 12, null, null, 2, null, null, 4, 3, null, null, 9, null, null};
//        index = 0;
//        System.out.println(isFull(createBT(myArr)));
        System.out.println(1 << 1);
        System.out.println(1 << 2);
        System.out.println(1 << 3);
        System.out.println(1 << 4);
    }

    public static boolean isFull(Node x) {
        Info process = process(x);
        return (1 << process.height) == process.nodes + 1;
    }

    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info left = process(x.left);
        Info right = process(x.right);
        int nodes = left.nodes + right.nodes + 1;
        int height = Math.max(left.height, right.height) + 1;
        return new Info(nodes, height);
    }

    static class Info {
        int nodes;
        int height;

        public Info(int nodes, int height) {
            this.nodes = nodes;
            this.height = height;
        }
    }


    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node createBT(Integer[] arr) {
        if (arr == null || arr.length <= 0) {
            return null;
        }
        return create(arr);
    }

    // 借助全局变量实现
    public static Node create(Integer[] arr) {
        Integer value = arr[index++];
        //System.out.printf("index:%d, arr[index]:%d\n", index, value);
        if (value == null) {
            return null;
        }
        final Node node = new Node(value);
        node.left = create(arr);
        node.right = create(arr);
        return node;
    }
}
